package com.mgq.algorithm.forcerecursive;

/**
 * @author MaGuangQi
 * 背包问题
 * 给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表
 * i号物品的重量和价值。给定一一个正数bag，表示一个载重bag的袋子，你装的物
 * 品不能超过这个重量。返回你能装下最多的价值是多少?
 * @date 2022-01-07 15:24
 **/
public class Knapsack {

  //此方法不正确
   /* public static int process(int[] weight, int[] values, int i, int alreadyWeight, int bag) {
        System.out.println("alreadyWeight: "+alreadyWeight);
        if (alreadyWeight > bag) {
            return 0;
        }
        //0->i-1 i到length时,超过了,返回0
        if (i == weight.length) {
            return 0;
        }
        //不选择
        int noIncludeCur = process(weight, values, i+1, alreadyWeight, bag);
        //选择
        int includeCur = values[i]+process(weight, values, i + 1, alreadyWeight + weight[i], bag);

        return Math.max(noIncludeCur, includeCur);
    }*/
    /**
     * 货物自由选择,返回价值最大的
     *
     * @param weight
     * @param values
     * @param i
     * @param alreadyWeight
     * @param bag
     * @return
     */
    public static int process2(int[] weight, int[] values, int i, int alreadyWeight,int alreadyValue, int bag) {
        System.out.println("alreadyWeight: "+alreadyWeight);
        if (alreadyWeight > bag) {
            return 0;
        }
        //0->i-1 i到length时,超过了,返回0
        if (i == weight.length) {
            return alreadyValue;
        }
        //不选择
        int noIncludeCur = process2(weight, values, i+1, alreadyWeight,alreadyValue, bag);
        //选择
        int includeCur = process2(weight, values, i + 1, alreadyWeight + weight[i],alreadyValue+values[i], bag);

        return Math.max(noIncludeCur, includeCur);
    }
    public static void main(String[] args) {
        int process = process2(new int[]{1, 2, 3}, new int[]{5, 3, 7}, 0, 0,0, 3);
        System.out.println(process);
    }
}
